#include <linkedlist.h>
#include <stdlib.h>
#include <assert.h>

/**
 * 创建新节点
 */
static listnode* new_node(int val) {
    listnode* node = (listnode*)malloc(sizeof(listnode));
    node->next = NULL;
    node->val  = val;
    return node;
}

/**
 * 移动到第n个节点
 */
static listnode* move_to(linkedlist* list, int position) {
    assert(list != NULL && position >= 1 && position <= list->length);
    listnode *node = list->head->next;
    for (int i = 1; i < position && node != NULL; i++, node = node->next);
    return node;
}

linkedlist *new_linkedlist() {
    linkedlist* list = (linkedlist*)malloc(sizeof(linkedlist));
    listnode * head  = new_node(-1);
    list->length = 0;
    list->head = head;
    return list;
}

unsigned linkedlist_length(const linkedlist* list) {
    assert(list != NULL);
    return list->length;
}

linkedlist *linkedlist_insert(linkedlist *list, int val, int position) {
    assert(list != NULL);
    // 空表直接插入
    if (linkedlist_empty(list)) {
        listnode * node = new_node(val);
        list->head->next = node;
        list->length += 1;
        return list;
    }
    // 非空表，顺着指针往下找         
    listnode *node = move_to(list, position);
    if (NULL != node) {
        listnode *n = new_node(val);
        n->next = node->next;
        node->next = n;
        list->length += 1;
    }
    return list;
}

linkedlist *linkedlist_append(linkedlist *list, int val) {
    return linkedlist_insert(list, val, list->length);
}

int linkedlist_remove(linkedlist *list, int position) {
    assert(list != NULL && position >= 1 && position <= list->length);
    listnode *node = list->head->next;
    listnode *prev = list->head;
    for (int i = 1; i < position && node != NULL; i++, prev = node, node = node->next);
    int ret = 0;
    if (node != NULL) {
        ret = node->val;
        prev->next = node->next;
        node->next = NULL;
        free(node);
        list->length -= 1;
    }
    return ret;
}

void linkedlist_for_each(linkedlist *list, linkedlist_visitor visitor) {
    assert(list != NULL);
    listnode *node = list->head->next;
    while (node) {
        visitor(node->val);
        node = node->next;
    }
}

int linkedlist_empty(linkedlist* list) {
    assert(list != NULL);
    return 0 == list->length;
}

int linkedlist_get_at(linkedlist *list, int position) {
    listnode *n = move_to(list, position);
    if (n != NULL) {
        return n->val;
    }
    return 0;
}

/**
 * 修改链表的第position个位置的元素
 * @param val 新的值
 * @param position 元素位置
 */
void linkedlist_set_at(linkedlist *list, int val, int position) {
    listnode *n = move_to(list, position);
    if (n != NULL) {
        n->val = val;
    }
}

void linkedlist_release(linkedlist *list) {
    assert(list != NULL);
    listnode *node = list->head->next;
    while (node) {
        listnode *p = node->next;
        free(node);
        node = p;
    }
    free(list);
}

